﻿#define  _CRT_SECURE_NO_WARNINGS 1

//23. 等差数列划分

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);

        int sum = 0;
        for (int i = 2; i < n; ++i)
        {
            dp[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] ? dp[i - 1] + 1 : 0;
            sum += dp[i];
        }
        return sum;
    }
};



//24. 最⻓湍流⼦数组
//f[i] 表⽰：以 i 位置元素为结尾的所有⼦数组中，最后呈现「上升状态」下的最⻓湍流数组的⻓度；
//g[i] 表⽰：以 i 位置元素为结尾的所有⼦数组中，最后呈现「下降状态」下的最⻓湍流数组的⻓度。
class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        vector<int> f(n, 1), g(n, 1);

        int ret = 1;
        for (int i = 1; i < n; ++i)
        {
            if (arr[i - 1] < arr[i]) f[i] = g[i - 1] + 1;
            else if (arr[i - 1] > arr[i]) g[i] = f[i - 1] + 1;

            ret = max(ret, max(f[i], g[i]));
        }
        return ret;
    }
};



//25. 单词拆分
//dp[i] 表⽰：[0, i] 区间内的字符串，能否被字典中的单词拼接⽽成。
//对于 dp[i] ，为了确定当前的字符串能否由字典⾥⾯的单词构成，根据最后⼀个单词的起始位
//置 j ，我们可以将其分解为前后两部分：
//i.前⾯⼀部分[0, j - 1] 区间的字符串；
//ii.后⾯⼀部分[j, i] 区间的字符串。
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> hash;
        for (auto& s : wordDict) hash.insert(s);
        int n = s.size();
        vector<bool> dp(n + 1);

        dp[0] = true;
        s = ' ' + s;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = i; j >= 1; j--)
            {
                if (dp[j - 1] && hash.count(s.substr(j, i - j + 1)))
                {
                    dp[i] = true;
                    break;
                }

            }
        }
        return dp[n];
    }
};

